/* Coded for sigMatch
 * Author: Ramakrishnan Kandhan (ramak@cs.wisc.edu)
 *
 * ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2000 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 *
 * Portions of this software are based upon public domain software
 * originally written at the National Center for Supercomputing Applications,
 * University of Illinois, Urbana-Champaign.
 */


/*
 *
 * Bloom Filter code in C 
 * Coded by rk
 *
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H

namespace sigMatch {

//define the constants
const unsigned int char_size = 0x08;    // 8 bits in 1 char(unsigned)
const unsigned char bit_mask[8] = {
                                   0x01, //00000001
                                   0x02, //00000010
                                   0x04, //00000100
                                   0x08, //00001000
                                   0x10, //00010000
                                   0x20, //00100000
                                   0x40, //01000000
                                   0x80  //10000000
                                 };


inline
unsigned long fast_hash(char *buf, int len)
{
  unsigned long hval = 0;

  unsigned char *bptr = (unsigned char*) buf;    /* start of buffer */
  unsigned char *bend = bptr + len;             /* beyond end of buffer */

  while (bptr < bend)
    hval = hval * 31UL + *bptr++;

  return hval;
}

inline
unsigned int xor_hash(char *buf, int len)
{
  unsigned int hash_val = 0;

  hash_val ^= *((unsigned int *) (buf));
  hash_val ^= *((unsigned int *) (buf+1));
  hash_val ^= *((unsigned int *) (buf+2));

  return hash_val;
}

unsigned int RSHash(char* str, unsigned int len)
{
   unsigned int b    = 378551;
   unsigned int a    = 63689;
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = hash * a + (*str);
      a    = a * b;
   }

   return hash;
}

unsigned int JSHash(char* str, unsigned int len)
{
   unsigned int hash = 1315423911;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash ^= ((hash << 5) + (*str) + (hash >> 2));
   }

   return hash;
}

inline int hashfunc1(char *s, int l)
{
	return xor_hash(s,l);
}

inline int hashfunc2(char *s, int l)
{
	return RSHash(s,l);
}

typedef struct bloomf{
	unsigned char* hash_table;
	unsigned int   table_size;
} bloomf;


void initbloomf (bloomf* bf, unsigned int size) 
{
	bf->table_size = size;
	bf->hash_table = (unsigned char*) malloc ((int) sizeof(unsigned char)* (int)(size/char_size));
}

void insertEntry ( bloomf* bf, char* str, int le )
{
	unsigned int hash1 = hashfunc1(str, le) % bf->table_size;
	bf->hash_table[hash1 / char_size] |= bit_mask[hash1 % char_size];
	unsigned int hash2 = hashfunc2(str, le) % bf->table_size;
	bf->hash_table[hash2 / char_size] |= bit_mask[hash2 % char_size];
}

inline int bloomcontains(bloomf* bf, char *str, int le)
{
	unsigned int hash1 = xor_hash(str, le) % bf->table_size;
    unsigned int bit  = hash1 % char_size;
   	if ((bf->hash_table[hash1 / char_size] & bit_mask[bit]) != bit_mask[bit])
    {
    	return 0;
    }

	unsigned int hash2 = fast_hash(str, le) % bf->table_size;
    bit  = hash2 % char_size;
   	if ((bf->hash_table[hash2 / char_size] & bit_mask[bit]) != bit_mask[bit])
    {
    	return 0;
    }

	return 1;
}

}
#endif
